public class Solution {

    public boolean hasPath(char[] matrix, int rows, int cols, char[] str) {
        //矩阵中每一个格子作为路径的起点
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                int[] flag = new int[matrix.length];
                if (hasPath(matrix, rows, cols, str, i, j, 0, flag)) {
                    return true;
                }
            }
        }
        return false;
    }

    /**
     * 查找
     *
     * @param matrix 使用以为坐标储存二维坐标的数据
     * @param rows   该二维数组有多少行
     * @param cols   该二维数组有多少列
     * @param str    要查找的路径
     * @param i      当前的横坐标
     * @param j      当前的纵坐标
     * @param k      查找的次数
     * @param flag   经过的坐标（经过之后设置为1）
     * @return
     */
    private boolean hasPath(char[] matrix, int rows, int cols, char[] str, int i, int j, int k, int[] flag) {
        //计算当前坐标在一维数组中的位置
        int index = cols * i + j;
        //判断 计算的位置是否越界  判断横坐标纵坐标是否越界  判断是否曾经经过坐标  判断是否相等
        if (index >= matrix.length || i < 0 || j < 0 || i > rows || j > cols || flag[index] == 1 || matrix[index] != str[k]) {
            return false;
        }

        if (k == str.length - 1) {
            return true;
        }
        if (matrix[index] == str[k]) {

            flag[index] = 1;
            //向左查找
            return hasPath(matrix, rows, cols, str, i, j - 1, k + 1, flag) ||
                    //向下查找
                    hasPath(matrix, rows, cols, str, i + 1, j, k + 1, flag) ||
                    //向右查找
                    hasPath(matrix, rows, cols, str, i, j + 1, k + 1, flag) ||
                    //向上查找
                    hasPath(matrix, rows, cols, str, i - 1, j, k + 1, flag);

        }
        return false;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.hasPath("ABCESFCSADEE".toCharArray(), 3, 4,
                "ABCCED".toCharArray()) + "[true]");// true
        //ABCE //SEE
        //SFCS
        //ADEE
        System.out.println(solution.hasPath("ABCESFCSADEE".toCharArray(), 3, 4,
                "SEE".toCharArray()) + "[true]");// true
        //ABCE //ABCB
        //SFCS
        //ADEE
        System.out.println(solution.hasPath("ABCESFCSADEE".toCharArray(), 3, 4,
                "ABCB".toCharArray()) + "[false]");// false
        //ABCEHJIG //SLHECCEIDEJFGGFIE
        //SFCSLOPQ
        //ADEEMNOE
        //ADIDEJFM
        //VCEIFGGS
        System.out.println(solution.hasPath("ABCEHJIGSFCSLOPQADEEMNOEADIDEJFMVCEIFGGS".toCharArray(), 5, 8,
                "SLHECCEIDEJFGGFIE".toCharArray()) + "[true]");// true
        //ABCEHJIG //SGGFIECVAASABCEHJIGQEM
        //SFCSLOPQ //
        //ADEEMNOE
        //ADIDEJFM
        //VCEIFGGS
        System.out.println(solution.hasPath("ABCEHJIGSFCSLOPQADEEMNOEADIDEJFMVCEIFGGS".toCharArray(), 5, 8,
                "SGGFIECVAASABCEHJIGQEM".toCharArray()) + "[true]");// true
        //ABCEHJIG //SGGFIECVAASABCEEJIGOEM
        //SFCSLOPQ
        //ADEEMNOE
        //ADIDEJFM
        //VCEIFGGS
        System.out.println(solution.hasPath("ABCEHJIGSFCSLOPQADEEMNOEADIDEJFMVCEIFGGS".toCharArray(), 5, 8,
                "SGGFIECVAASABCEEJIGOEM".toCharArray()) + "[false]");// false
        //ABCEHJIG //SGGFIECVAASABCEHJIGQEMS
        //SFCSLOPQ
        //ADEEMNOE
        //ADIDEJFM
        //VCEIFGGS
        System.out.println(solution.hasPath("ABCEHJIGSFCSLOPQADEEMNOEADIDEJFMVCEIFGGS".toCharArray(), 5, 8,
                "SGGFIECVAASABCEHJIGQEMS".toCharArray()) + "[false]");// false
        //AAAA //AAAAAAAAAAAA
        //AAAA
        //AAAA
        System.out.println(solution.hasPath("AAAAAAAAAAAA".toCharArray(), 3, 4,
                "AAAAAAAAAAAA".toCharArray()) + "[true]");// true
        //AAAA //AAAAAAAAAAAAA
        //AAAA
        //AAAA
        System.out.println(solution.hasPath("AAAAAAAAAAAA".toCharArray(), 3, 4,
                "AAAAAAAAAAAAA".toCharArray()) + "[false]");// false

    }
}